/**
 * @file 300.LongestIncreasingSubseq.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-17
 * 
 * @copyright Copyright (c) 2021
 * 
 * 子序列问题
 * 53.最大子序和 -- 连续
 * 674.最长连续递增序列长度 -- 连续 * 
 * 300.最长递增子序列
 * 673.最长递增子序列的个数 -- 个数 -- 300.进阶 难
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 53. 最大子序和：找到具有最大和的连续子数组
    int maxSubArray(vector<int> &nums)
    {
        // dp[i] 以nums[i]结尾的最大子序和（必包括nums[i]）
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        int maxDp = dp[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            maxDp = max(maxDp, dp[i]);
        }
        print(dp);
        return maxDp;
    }
    // 674.
    int findLengthOfLCIS(vector<int> &nums)
    {
        // 感觉需要2个变量，一个记录历史最长连续递增序列长度
        // 一个统计当前连续递增序列长度
#if 0
        int n = nums.size();
        int oldLCIS = 1;
        int newLCIS = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                ++newLCIS;
            } else {
                oldLCIS = max(oldLCIS, newLCIS);
                newLCIS = 1;
            }
        }
        return max(oldLCIS, newLCIS);
#endif
        // dp[i] 到第i个元素为止，最长连续递增序列的长度
        int n = nums.size();
        vector<int> dp(n, 1);
        int res = 1;
        for (int i = 1; i < n; ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            res = max(res, dp[i]);
        }
        return res;
    }
    // 300. LIS
    int lengthOfLIS(vector<int> &nums)
    {
        // 子序列入门 dp O(N^2) 此题还有更优解，暂不考虑
        // dp[i] 表示到第i个元素为止，最长递增子序列的长度
        // 考虑第i个元素会不会对LIS做出贡献，枚举j从0到i
        int n = nums.size();
        vector<int> dp(n, 1);
        dp[0] = 1;
        int maxDp = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxDp = max(maxDp, dp[i]);
        }
        // print(dp);
        return maxDp;
    }
    // 673. 最长递增子序列**个数**
    int findNumberOfLIS(vector<int> &nums)
    {
        // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
        // cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数
        int n = nums.size();
        vector<int> dp(n, 1);
        vector<int> cnt(n, 1);
        int maxDp = 1;
        int maxCnt = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxDp) {
                maxDp = dp[i];
                maxCnt = cnt[i];
            } else if (dp[i] == maxDp) {
                maxCnt += cnt[i];
            }
        }
        // print(dp);
        // print(cnt);
        return maxCnt;
    }
};
void test53()
{
    vector<int> nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> nums2 = {1};
    vector<int> nums3 = {0};
    vector<int> nums4 = {-1};
    vector<int> nums5 = {-100000};
    cout << Solution().maxSubArray(nums1) << endl;
    cout << Solution().maxSubArray(nums2) << endl;
    cout << Solution().maxSubArray(nums3) << endl;
    cout << Solution().maxSubArray(nums4) << endl;
    cout << Solution().maxSubArray(nums5) << endl;
}

void test674()
{
    vector<int> nums1 = {1, 3, 5, 4, 7};
    vector<int> nums2 = {1, 3, 5, 4, 7, 9, 10};
    vector<int> nums3 = {1, 1, 1, 1, 1, 1};
    cout << Solution().findLengthOfLCIS(nums1) << endl;
    cout << Solution().findLengthOfLCIS(nums2) << endl;
    cout << Solution().findLengthOfLCIS(nums3) << endl;
}

void test300()
{
    vector<int> nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> nums2 = {0, 1, 0, 3, 2, 3};
    vector<int> nums3 = {1, 1, 1, 1, 1, 1};
    vector<int> nums4 = {1, 3, 6, 7, 9, 4, 10, 5, 6};
    cout << Solution().lengthOfLIS(nums1) << endl;
    cout << Solution().lengthOfLIS(nums2) << endl;
    cout << Solution().lengthOfLIS(nums3) << endl;
    cout << Solution().lengthOfLIS(nums4) << endl;
}

void test673()
{
    vector<int> nums1 = {1, 3, 5, 4, 7};
    vector<int> nums2 = {1, 3, 5, 4, 7, 9, 10};
    vector<int> nums3 = {1, 1, 1, 1, 1, 1};
    cout << Solution().findNumberOfLIS(nums1) << endl; // 2
    cout << Solution().findNumberOfLIS(nums2) << endl; // 2
    cout << Solution().findNumberOfLIS(nums3) << endl; // 6
}

int main()
{
    // test53();
    // test674();
    // test300();
    test673();
    return 0;
}